/*
 * graph2D
 * Copyright (c) 2009 Shun Moriya <shun@mnu.sakura.ne.jp>
 *
 * The MIT License
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#if !defined(___GRAPH2D_CURVE_H___)
#define ___GRAPH2D_CURVE_H___

#if !defined(___GRAPH2D_VECTOR2_H___)
#include "vector2.h"
#endif

#include <cmath>
#include <cstddef>
#include <cstring>

namespace Graph2D
{
	/*!
	 * @brief カーブキーフレームクラス
	 */
	template <class VALUE_TYPE> struct CurveKey
	{
		/*!
		 * @brief カーブキーフレームの補完関数の種類
		 */
		typedef enum InterpolationType
		{
			INTERPOLATION_CONST,		//!< @brief 定数
			INTERPOLATION_LINER,		//!< @brief 線形補間
			INTERPOLATION_HERMITE,		//!< @brief エルミートスプライン
			INTERPOLATION_CATMULL,		//!< @brief Catmull-Romスプライン
			INTERPOLATION_SLERP,		//!< @brief 球面線形補間
			INTERPOLATION_SQUAD,		//!< @brief 球面３次補間
			INTERPOLATION_COUNT
		}InterpolationType;

		InterpolationType interpolationType;	//!< @brief カーブキーフレームの補完関数の種類
		float second;							//!< @brief キーフレームの時間
		VALUE_TYPE value;						//!< @brief キーフレームの値


		/*!
		 * @brief	カーブキーフレームの補完関数の種類を取得
		 * @return	カーブキーフレームの補完関数の種類
		 */
		InterpolationType getInterpolationType() const
		{
			return interpolationType;
		}

		/*!
		 * @brief	カーブキーフレームの補完関数の種類を設定
		 * @param[in]	interpolationType	カーブキーフレームの補完関数の種類
		 */
		void setInterpolationType(const InterpolationType interpolationType)
		{
			this->interpolationType = interpolationType;
		}

		/*!
		 * @brief	キーフレームの時間を取得
		 * @return	キーフレームの時間
		 */
		float getTime() const
		{
			return second;
		}

		/*!
		 * @brief	キーフレームの時間を設定
		 * @param[in]	second	キーフレームの時間
		 */
		void setTime(const float second)
		{
			this->second = second;
		}

		/*!
		 * @brief		キーフレーム間の時間を取得
		 * @param[in]	curveKey	対象になるキーフレームオブジェクト
		 * @return		キーフレーム間の時間
		 */
		float getTimeSpan(const CurveKey* curveKey) const
		{
			return curveKey ? curveKey->getTime() - second : 0;
		}

		/*!
		 * @brief		キーフレーム間の時間を取得
		 * @param[in]	curveKey	対象になるキーフレームオブジェクト
		 * @return		キーフレーム間の時間
		 */
		float getTimeSpan(const CurveKey& curveKey) const
		{
			return curveKey.getTime() - second;
		}

		/*!
		 * @brief	キーフレームの値を取得
		 * @return	キーフレームの値
		 */
		const VALUE_TYPE& getValue() const
		{
			return value;
		}

		/*!
		 * @brief	キーフレームの値を設定
		 * @param[in]	value	キーフレームの値
		 */
		void setValue(const VALUE_TYPE& value)
		{
			this->value = value;
		}
	};

	////////////////////////////////////////////////////////////////////////////////
	/*!
	 * @brief カーブクラス
	 */
	template <class KEY, class VALUE_TYPE> class Curve
	{
	public:
		/*!
		 * @brief	コンストラクタ
		 */
		Curve()
			: curveKeys(NULL)
			, curveKeyCount(0)
			, referenced(false)
			, normalized(false)
		{
		}

		/*!
		 * @brief	デストラクタ
		 */
		virtual ~Curve()
		{
			releaseKeyData();
		}

		/*!
		 * @brief	カーブキーフレームデータを設定
		 * @param[in]	count		カーブキーフレームデータの数
		 * @param[in]	curveKey	カーブキーフレームデータ
		 * @param[in]	reference	カーブキーフレームデータを参照する
		 */
		void setKeyData(const size_t count, KEY* curveKey, const bool reference)
		{
			releaseKeyData();

			if(reference)
			{
				curveKeys = curveKey;
			}
			else
			{
				curveKeys = new KEY[count];
				if(curveKeys)
					memcpy(const_cast<KEY*>(curveKeys), curveKey, sizeof(KEY) * count);
			}

			curveKeyCount = count;
			referenced = reference;
			normalized = false;
		}

		/*!
		 * @brief	カーブキーフレームを取得
		 */
		const KEY& getKeyFrame(const size_t index) const
		{
			return curveKeys[index];
		}

		/*!
		 * @brief	カーブの総時間を取得
		 * @return	カーブの総時間
		 */
		float getLength()
		{
			const int count = getKeyCount();
			if(count <= 1)
				return 0;

			if(!normalized)
				normalize();

			return curveKeys[0].getTimeSpan(curveKeys[count - 1]);
		}

		/*!
		 * @brief	カーブキーフレームデータの個数を取得
		 * @return	カーブキーフレームデータの個数
		 */
		size_t getKeyCount() const
		{
			return curveKeyCount;
		}

		/*!
		 * @brief		指定した時間の時の値を取得
		 * @param[in]	時間
		 * @return		値
		 */
		VALUE_TYPE getValue(const float second)
		{
			if(!normalized)
				normalize();

			const KEY* skey  = NULL;
			const KEY* ekey  = NULL;
			const KEY* sskey = NULL;
			const KEY* eekey = NULL;

			for(size_t i = 0; i < getKeyCount(); i++)
			{
				if(curveKeys[i].getTime() > second)
				{
					ekey  = &curveKeys[i];
					skey  = i > 0 ? &curveKeys[i - 1] : ekey;
					sskey = i > 1 ? &curveKeys[i - 2] : skey;
					eekey = i < (getKeyCount() - 1) ? &curveKeys[i + 1] : ekey;
					break;
				}
			}

			if(!ekey)
			{
				return curveKeys[getKeyCount() - 1].getValue();
			}
			else if(skey == ekey)
			{
				return curveKeys[0].getValue();
			}

			VALUE_TYPE p0 = skey->getValue();
			VALUE_TYPE p1 = ekey->getValue();
			const float st = (float)skey->getTime();
			const float et = (float)ekey->getTime();
			const float nt = (float)second;
			const float t  = ((nt - st) /(et - st));

			switch(skey->getInterpolationType())
			{
				case CurveKey<VALUE_TYPE>::INTERPOLATION_CONST:
					return p0;

				case CurveKey<VALUE_TYPE>::INTERPOLATION_LINER:
					return (p0 + (p1 - p0) * t);
					break;

				case CurveKey<VALUE_TYPE>::INTERPOLATION_HERMITE:
				{
					VALUE_TYPE p3 = eekey->getValue();
					VALUE_TYPE v0 = p1 - p0;
					VALUE_TYPE v1 = p3 - p1;
					return (p0 * 2 - p1 * 2 + v0 + v1) * (t * t * t) + (p0 * (-3) + p1 * 3 - v0 * 2 - v1) * (t * t) + v0 * t + p0;
				}

				case CurveKey<VALUE_TYPE>::INTERPOLATION_CATMULL:
				{
					VALUE_TYPE p2 = sskey->getValue();
					VALUE_TYPE p3 = eekey->getValue();
					VALUE_TYPE v0 = (p1 - p2) * 0.5f;
					VALUE_TYPE v1 = (p3 - p0) * 0.5f;
					return (p0 * 2 - p1 * 2 + v0 + v1) * (t * t * t) + (p0 * (-3) + p1 * 3 - v0 * 2 - v1) * (t * t) + v0 * t + p0;
				}

				case CurveKey<VALUE_TYPE>::INTERPOLATION_SLERP:
				{
					const float theta = 3.14159265358979323846f / 2.f;
					return (p0 * sinf(theta * (1 - t)) + p1 * sinf(theta * t)) / sinf(theta);
				}

				default:
					return VALUE_TYPE();
			}
		}

		/*!
		 * キーフレームデータが正規化を必要になった事を設定
		 */
		void dirty()
		{
			normalized = false;
		}

	private:
		/*!
		 * @brief	キーフレームを正規化
		 */
		void normalize()
		{
			int gap  = getKeyCount();
			bool done = false;

			while((gap > 1) || done == false)
			{
				gap = (gap * 10) / 13;
				if(gap == 0)
					gap = 1;
				done = true;
				for(size_t i = 0; i < getKeyCount() - gap; ++i)
				{
					if(curveKeys[i].getTime() > curveKeys[i + gap].getTime())
					{
						const KEY temp     = curveKeys[i];
						curveKeys[i      ] = curveKeys[i + gap];
						curveKeys[i + gap] = temp;
						done = false;
					}
				}
			}

			for(size_t i = 0; i < getKeyCount() - 1; i++)
			{
				if(curveKeys[i].getTime() != curveKeys[i + 1].getTime())
					continue;
				/*
				 for(int j = i + 1; j < getKeyCount(); j++)
				 curveKeys[j]->setTime(curveKeys[j]->getTime() + 1);
				 */
			}

			normalized = true;
		}

		/*!
		 * @brief	カーブキーフレームデータを解放
		 */
		void releaseKeyData()
		{
			if(!referenced)
			{
				delete []curveKeys;
			}
			curveKeys = NULL;
		}

	private:
		KEY* curveKeys;			//!< @brief カーブキーフレームデータ
		size_t curveKeyCount;	//!< @brief カーブキーフレームの数
		bool referenced;		//!< @brief カーブキーフレームデータが参照アドレスを表すフラグ
		bool normalized;		//!< @brief 正規化済みフラグ
	};

	typedef CurveKey<float> ScalarCurveKey;
	typedef CurveKey<Vector2> Vector2CurveKey;

	typedef Curve<ScalarCurveKey, float> ScalarCurve;
	typedef Curve<Vector2CurveKey, Vector2> Vector2Curve;
}

#endif
